package com.freedy.dataStructure.tree;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;


/**
 * @author Freedy
 * @date 2021/3/25 21:16
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr={13,7,8,3,29,6,1};
        BinaryTree.Node<Integer> node = buildHuffmanTree(arr);
        node.preOrder();
        System.out.println(node);
    }

    public static BinaryTree.Node<Integer> buildHuffmanTree(int[] arr){
        List<BinaryTree.Node<Integer>> nodeList = Arrays.
                stream(arr).boxed().map(BinaryTree.Node::new).
                sorted(Comparator.comparingInt(BinaryTree.Node::getData)).
                collect(Collectors.toList());
       while (nodeList.size()>1){
           BinaryTree.Node<Integer> left = nodeList.get(0);
           BinaryTree.Node<Integer> right = nodeList.get(1);
           BinaryTree.Node<Integer> parent = new BinaryTree.Node<>(left.getData()+right.getData(),left,right);
           nodeList.remove(0);
           nodeList.remove(0);
           nodeList.add(parent);
           nodeList.sort(Comparator.comparingInt(BinaryTree.Node::getData));
       }
       return nodeList.get(0);
    }
}
